A portion of the disclosure of this patent document contains material which is subject to (copyright or mask work) protection. The (copyright or mask work) owner has no objection to facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent And Trademark Office patent file or records, but otherwise reserves all (copyright or mask work) rights whatsoever.
The present application incorporates by reference the computer program listing in the appendix on one compact disc. The file names on the disk are
borderline.cxe2x80x946 KB;
bud.cxe2x80x948 KB;
canvas.cxe2x80x9420 KB;
copyright.1989xe2x80x941 KB;
defines.hxe2x80x947 KB;
demo.cxe2x80x941 KB;
externs.hxe2x80x9412 KB;
globals.hxe2x80x9411 KB;
init.cxe2x80x944 KB;
interpol.cxe2x80x9418 KB;
metric.cxe2x80x942 KB;
path.cxe2x80x945 KB;
print.cxe2x80x942 KB;
show.cxe2x80x9411 KB;
trafo_data.cxe2x80x9410 KB .
The CD-ROM lists the creation date of the files as December 23, 2001, which was the date of the creation of the compact disc layout. The files were copied onto the compact disc on December 25, 2001.
1. Field of the Invention
The invention relates to planning an optimal path for an object to follow from a given start point to a nearest one of a set of goals, taking into account constraints and obstacles.
2. The Prior Art
One of the most important outstanding problems in robotics is that of path planning with obstacle avoidance. In a typical task, the robot has to move from a start location to a goal location. Obstacles should be avoided along the way, and the movement as a whole should be as efficient as reasonably possible. The planning of the path should be as rapid as possible. The problem of providing such a xe2x80x9cpathxe2x80x9d for a robot, for instance by giving a series of set points, is called the path planning problem.
There are a number of existing robots. Typically they are controlled using a programming language. One commonly used language is Val II, described in Unimation, Inc., xe2x80x9cProgramming Manual: User""s Guide to Val II: Version 2.0 398AG1xe2x80x9d, December 1986. Val II can be used to control products such as Unimation""s Puma Robots and Adept Robots. Using Val II, a user can specify the movement of a robot, from a current point to a desired point, using the command MOVE POINT () on page 4-20 of the reference. Points are usually generated in joint coordinates. It is therefore sufficient for a path planning method to generate a series of set points to be inserted in the appropriate Val II command. The technology is in place for the robot to follow a path once the set points are generated.
Typical industrial robots use manually generated set points. Such manually generated set points are adequate for performing a simple repetitive task such as automated assembly in an environment which does not change from one task to the next. Manually generated set points are not practical and paths followed are often not efficient for dynamic situations, or for situations with large numbers of obstacles, or for obstacles with complex shapes. Therefore there is a need for a method to generate set points automatically.
One known method automatically generates a set of points along an optimal path. The set of points allows a robot to get from a start point to one of a set of goal points. One goal point is chosen over the others because it minimizes movement of the robot. This known method is disclosed in L. Dorst et al., xe2x80x9cThe Constrained Distance Transformation, A Pseudo-Euclidean, Recursive Implementation of the Lee-algorithmxe2x80x9d, Signal Processing III (I. T. Young et al. eds; Elsevier Science Publishers B. V., EURASIP 1986) (xe2x80x9cL. Dorst et al.xe2x80x9d); and P. W. Verbeek et al., xe2x80x9cCollision Avoidance and Path Finding through Constrained Distance Transformation in Robot State Spacexe2x80x9d, Proc. Conf. Dec. 8-11 1986, Amsterdam pp. 627-634. The known method plans paths in the configuration space of the robot. Obstacles to robot movement are represented by forbidden states in configuration space. In this space, the series of set points is represented in so-called joint coordinates, this is a set of coordinates that can be used to drive the joints of the robot directly. No complicated coordinate transformations are needed. An advantage of the known method is the simplicity with which it can be expanded to greater numbers of degrees of freedom.
In the prior art, the path in configuration space is found in three steps:
1) A transformation is made of the obstacles and the goals of the robot from points in task space to states in configuration space, The configuration space is discretized.
2) A cost field is created, specifying the total cost needed to reach the closest goal state at each state in configuration space. The particular method used to produce the cost field is described in L. Dorst et al. The method is a repeated scanning of the complete configuration space, while performing a basic cost propagation operation at each state.
3) From the start state, steps are taken in the direction of the cost gradient of the cost field until the goal state is reached. The states passed on the way form the shortest path from start to goal, and can be used as the series of set points.
Steps 1) and 2) are performed only once for a given robot and a given set of obstacles and goals. Using the same cost field, Step 3) can be performed for different start states.
The prior art method has a number of disadvantages. First, in step 2), the whole configuration space has to be scanned several times. Second, the kinds of cost metrics considered are restricted. In particular the cost of transitions between states in configuration space are considered to be the same for a given direction independent of the state at which cost is calculated. These restrictions limit practical applications. For instance, it is not possible to find a path for a robot arm with revolute joints that will result in minimal movement of an end-effector. Minimal time paths are only possible for a few robots which are of limited practical application. A third disadvantage is that following the gradient requires computation of the gradient at every point of the path.
It is an object of the invention to avoid repeated scanning of the configuration space during creation of the cost field.
It is a second object of the invention to allow use of cost metrics which vary at different states in configuration space. An example of this would be a cost function which allows minimization of the movement of the effector end of the robot.
It is a third object of the invention to avoid computation of the gradient at every state during establishment of a path.
It is a fourth object of the invention to create a path planning method which is easily adaptable to multiple degrees of freedom.
These objects are achieved according to the invention by a process referred to herein as xe2x80x9cbudding.xe2x80x9d
These objects are further achieved according to the invention by the use of cost metrics which are referred to herein as xe2x80x9cspace-variant metrics.xe2x80x9d
These objects are still further achieved according to the invention by a process referred to herein as xe2x80x9cfollowing the direction arrowsxe2x80x9d.
These objects are further achieved according to the invention by using the space-variant matrices in a multi-dimensional configuration space.
Further objects and advantages of the invention will become apparent in the remainder of the application.